#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;
/*
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if(digits.size()==0){
            //res.push_back("");
            return res;
        }
        vector<char> left;
        for(int i=0;i<digits.size();i++){
            left.push_back(digits[i]);
        }
        string s;
        dfs(left,s,res);
        return res;
    }
    void printDict(){
        for(auto& d:dict){
            cout<<d.first<<":";
            for(auto& c:d.second){
                cout<<c<<" ";
            }
            cout<<endl;
        }
    }
private:
    map<char,vector<char>> dict{{'2',{'a','b','c'}},{'3',{'d','e','f'}},{'4',{'g','h','i'}},{'5',{'j','k','l'}},{'6',{'m','n','o'}},{'7',{'p','q','r','s'}},{'8',{'t','u','v'}},{'9',{'w','x','y','z'}}};

    void dfs(vector<char>& left,string& str,vector<string>& res){
        if(left.size()==0){
            //return;
            res.push_back(str);
            return;
        }
        vector<char> tmp;
        char c;
        char d;
        for(int i=0;i<left.size();i++){
            c=left[i];
            tmp=dict[c];
            left.erase(left.begin()+i);
            for(int j=0;j<tmp.size();j++){
                d=tmp[j];
                str.push_back(d);
                tmp.erase(tmp.begin()+j);
                dfs(left,str,res);
                tmp.insert(tmp.begin()+j,d);
                str.pop_back();
            }
            left.insert(left.begin()+i,c);
            
        }
    }
};
*/
/*
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if(digits.size()==0){
            //res.push_back("");
            return res;
        }
        vector<char> left;
        for(int i=0;i<digits.size();i++){
            left.push_back(digits[i]);
        }
        string s;
        dfs(left,s,res);
        return res;
    }
    void printDict(){
        for(auto& d:dict){
            cout<<d.first<<":";
            for(auto& c:d.second){
                cout<<c<<" ";
            }
            cout<<endl;
        }
    }
    
private:
    map<char,vector<char>> dict{{'2',{'a','b','c'}},{'3',{'d','e','f'}},{'4',{'g','h','i'}},{'5',{'j','k','l'}},{'6',{'m','n','o'}},{'7',{'p','q','r','s'}},{'8',{'t','u','v'}},{'9',{'w','x','y','z'}}};

    void dfs(vector<char>& left,string& str,vector<string>& res){
        if(left.size()==0){
            //return;
            res.push_back(str);
            return;
        }
        vector<char> tmp;
        char c;
        char d;
        c=left[0];
        tmp=dict[c];
        left.erase(left.begin());
        for(int j=0;j<tmp.size();j++){
            d=tmp[j];
            str.push_back(d);
            tmp.erase(tmp.begin()+j);
            dfs(left,str,res);
            tmp.insert(tmp.begin()+j,d);
            str.pop_back();
        }
        left.insert(left.begin(),c);
    }
};
*/

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if(digits.size()==0){
            //res.push_back("");
            return res;
        }
        string str="";
        dfs(0,str,digits,res);
        return res;
    }

private:
    map<char,vector<char>> dict{{'2',{'a','b','c'}},{'3',{'d','e','f'}},{'4',{'g','h','i'}},{'5',{'j','k','l'}},{'6',{'m','n','o'}},{'7',{'p','q','r','s'}},{'8',{'t','u','v'}},{'9',{'w','x','y','z'}}};
    
    void dfs(int cur,string& str,string& dig,vector<string>& res){
        if(str.size()==dig.size()){
            res.push_back(str);
            return;
        }
        for(auto& c:dict[dig[cur]]){
            str.push_back(c);
            dfs(cur+1,str,dig,res);
            str.pop_back();
        }
    }
};

int main(){
    Solution s;
    //s.printDict();
    string in="23";
    vector<string> out=s.letterCombinations(in);
    for(int i=0;i<out.size();i++){
        cout<<out[i]<<endl;
    }
    return 0;
}